package com.sise.Tree;

/**
 *      230. 二叉搜索树中第K小的元素
 *
 *      给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
 *
 *      题解：
 *          利用二叉搜索树、结合中序遍历的升序特点
 */
public class _230_kthSmallest {

    public int kthSmallest(TreeNode root, int k) {
        traverse(root, k);              // 利用中序遍历的特性，左根右
        return res;
    }

    /**
     *  这里使用了额外的函数，返回值为 void，因为递归的过程中并不需要返回值，
     *  一开始的想法将 k 减到为 0 就退出，但这里会有一个问题， k 如果不是一直递归到最深处为 0 的话，
     *  那么就会回归到上一层， k 又变为原有值，故此需要一个全局变量 res，需要有一个 step ，每走一步就 +1。
     */

    int res = 0;    // 记录结果
    int step;       // 记录当前元素的排名
    private void traverse(TreeNode root, int k){
        if (root == null) return ;

        traverse(root.left, k);

        step++;
        if (k == step){         // 找到第 k 小的元素
            res =  root.val;
        }
        traverse(root.right, k);
    }
}
